#ifndef __SKIPLIST_H__
#define __SKIPLIST_H__

#include <cstdlib>
#include <cassert>
#include "SLNode.h"

using std::cout;
using std::endl;
static const double balFactor = 0.25;
static const int maxLevel = 32;

class SkipList
{
public:
    SkipList(int k)
    {
        createList(k);
    }
    ~SkipList()
    {
        freeList();
    }

    SLNode *search(int) const;

    bool insert(int);

    bool remove(int);

    void dumpAllNodes();

private:
    void createList(int);

    void freeList();

    void dumpNodeDetail(SLNode *, int);

    static int getRandomLevel();

private:
    int level;
    SLNode *head, *tail;

    size_t count;
};

int SkipList::getRandomLevel()
{
    int level = 1;

    while ((random() & 0xFFFF) < (balFactor * 0xFFFF))
    {
        ++level;
    }
    return maxLevel > level ? level : maxLevel;
}

void SkipList::createList(int lastVal)
{
    tail = new SLNode(lastVal, 1);
    head = new SLNode(0, maxLevel);
    for (int i = 0; i < maxLevel; ++i)
    {
        head->forward[i] = tail;
    }
    this->count = 0;
    this->level = 1;
}

void SkipList::freeList()
{
    SLNode *p = head, *q;
    while (p != nullptr)
    {
        q = p->forward[0];
        delete p;
        p = q;
    }
    delete p;
}

SLNode *SkipList::search(int key) const
{
    SLNode *node = head;
    for (int i = level-1; i >= 0; --i)
    {
        while ((node->forward[i])->key < key)
        {
            node = node->forward[i];
        }
    }

    node = node->forward[0];
    if (node->key == key)
    {
        return node;
    }
    else
    {
        return nullptr;
    }
}

bool SkipList::insert(int key)
{
    SLNode *update[maxLevel], *node = head;
    for (int i = level-1; i >= 0; --i)
    {
        while ((node->forward[i])->key < key)
        {
            node = node->forward[i];
        }
        update[i] = node;
    }

    node = node->forward[0];
    if (node->key == key)
    {
        return false;
    }

    int nodeLevel = getRandomLevel();
    if (nodeLevel > level)
    {
        nodeLevel = ++level;
        update[nodeLevel-1] = head;
    }

    SLNode *newNode = new SLNode(key, nodeLevel);

    for (int i = nodeLevel-1; i >= 0; --i)
    {
        node = update[i];
        newNode->forward[i] = node->forward[i];
        node->forward[i] = newNode;
    }
    ++count;
    return true;
}

bool SkipList::remove(int key)
{
    SLNode *update[maxLevel], *node = head;
    for (int i = level-1; i >= 0; --i)
    {
        while ((node->forward[i])->key < key)
        {
            node = node->forward[i];
        }
        update[i] = node;
    }
    node = node->forward[0];
    if (node->key != key)
    {
        return false;
    }

    for (int i = 0; i < level; ++i)
    {
        if (update[i]->forward[i] != node)
        {
            break;
        }
        update[i]->forward[i] = node->forward[i];
    }

    delete node;

    while (level > 1 && head->forward[level-1] == tail)
    {
        --level;
    }
    --count;

    return true;
}

void SkipList::dumpAllNodes()
{
    SLNode *tmp = head;
    while (tmp->forward[0] != tail)
    {
        tmp = tmp->forward[0];
        //dumpNodeDetail(tmp, tmp->nodeLevel);
        cout << tmp->key << "->" << tmp->nodeLevel << " ";
    }
    cout << endl;
}

void SkipList::dumpNodeDetail(SLNode *node, int nodeLevel)
{
    if (nullptr == node)
        return;
    cout << "node->key:" << node->key << ",node->value:" << endl;
    for (int i = 0; i <= nodeLevel; ++i)
    {
        cout << "forward[" << i << "]:"
             << "key:" << node->forward[i]->key
             << endl;
    }
    cout << "-----------" << endl;
}

#endif